Introduction to Combinatory Logic – #SoME2

This paragraph introduces the concept of combinatory logic, a system invented by Moses Schönfinkel in 1920 that eliminates the need for variables by using combinators. It explains the basic combinators 'i' (identity) and 'k', and how they can be combined to form new behaviors, like the 'n' combinator. The paragraph also sets the stage for a discussion on how any computer program, including one that calculates the Fibonacci sequence, can be written using just two functions, 's' and 'k'. The Fibonacci sequence is briefly mentioned as an example of a program that will be discussed in the video.

The second paragraph delves deeper into the behaviors of combinators 'b', 'c', and 's', which are used to perform function composition and carrying. It explains how these combinators can manipulate functions and their inputs to achieve different behaviors, such as applying one function to the result of another. The paragraph also provides examples of how these combinators can be used to create new ones with specific behaviors, like 'ci', 'sbi', 'skk', and 'sks', demonstrating that any program can be written using just 's', 'k', 'i', 'b', and 'c'. It concludes with the idea that since 'i', 'b', and 'c' can be expressed in terms of 's' and 'k', any program can be written using just two combinators.

This paragraph discusses the concept of recursion in programming and introduces the fixed point combinator 'y', which is essential for simulating recursive behavior in combinatory logic. It explains that 'y' allows a function to refer to itself without causing an infinite loop, and provides two different combinator expressions for 'y' discovered by Haskell Curry and Alan Turing. The paragraph also illustrates how to use 'y' to create a combinator expression for a self-referential function, using a modified version of a given function to avoid direct recursion.

The fourth paragraph explores how to simulate basic data structures like boolean values, ordered pairs, and natural numbers using combinatory logic. It describes how to represent true and false, and how to define logical operations like 'not'. The paragraph also explains how to simulate ordered pairs and access their elements, as well as how to represent natural numbers using pairs and the 'next' function. It discusses the concept of 'apply', a function that applies another function 'n' times to an input 'x', and how it can be defined using the 'y' combinator due to its self-referential nature.

This paragraph focuses on implementing the Fibonacci sequence using combinatory logic. It describes a function that takes two consecutive terms of the sequence and outputs the next two terms. The paragraph explains how to apply this function 'n' times to the initial pair (0,1) to obtain the nth number in the Fibonacci sequence. It also discusses the representation of numbers and the 'next pair' function, which is crucial for generating the sequence. The paragraph concludes with the expression for the Fibonacci program in terms of the basic combinators 's', 'k', 'i', 'b', and 'c'.

The final paragraph introduces the iota combinator, a universal combinator discovered by Chris Barker that can replace any other combinator in a program. It demonstrates that the iota combinator can be used to express all other combinators, making it possible to write any program using just iota. The paragraph also shows how the Fibonacci program can be written using the iota combinator. The video concludes with a thank you message from the creators, Alexander Faruja and Georgio Grigolo, who express their desire to share the basics of combinatory logic with the world.